1. Field of the Invention
The invention disclosed broadly relates to public key cryptography and more particularly relates to improvements in key generation and cryptographic applications in public key cryptography.
2. Related Art
The generation of a modulus as part of a public key according to the Rivest-Shamir-Adleman (RSA) cryptographic method is described in U.S. Pat. No. 4,405,829 (Rivest et al.), “Cryptographic Communications System and Method”, the disclosure of which is hereby incorporated by reference. In a set-up phase of the RSA scheme, a participant picks two prime numbers, p and q, each having a selected number of bits, such as 512 bits, with p not equal to q. The participant keeps p and q secret. The participant computes an RSA modulus n, with n=p*q. When p and q each have 512 bits, n has 1023 or 1024 bits. The participant picks an RSA exponent e that has no factors in common with (p−1)(q−1). For efficiency purposes, the RSA exponent e is often chosen of much shorter length than the RSA modulus. When the RSA modulus n has 1024 bits, the RSA exponent e typically has at most 64 bits. The owning participant makes the public key (n, e) available to other participants.
During operational use of the RSA scheme, other participants use the public key (n, e) to encrypt messages for the participant which owns that key. The owning participant is able to decrypt messages encrypted with the public key (n, e) due to possession of the secret prime numbers p and q.
Participants must store not only the public key of other participants, but also identifying information such as the name, address, account number and so on of the participant owning each stored public key. There are problems with this situation.
One problem with the present technique for using the RSA encryption scheme is that, although the RSA modulus n is 1024 bits, the amount of security provided actually corresponds to only 512 bits, since an attacker who knows one of p and q can readily obtain the other of p and q. Instead of having to store 1024 bits to obtain 512 truly secure bits, it is desirable to store far fewer bits, such as approximately 512 bits, to obtain the 512 truly secure bits.
Another problem with the present technique is that the long bit-length of the public keys imposes a significant bandwidth load on telecommunications devices, such as wireless telephone sets. It is desirable to reduce the amount of bandwidth load as much as possible.
Generating RSA moduli having a predetermined portion has been considered by Scott A. Vanstone and Robert J. Zuccherato in “Short RSA Keys and Their Generation”, J. Cryptology, 1995, volume 8, pages 101–114, the disclosure of which is hereby incorporated by reference.
In “Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known”, U. Maurer ed., EUROCRYPT '96 Proceedings, pages 178–189, Springer Verlag 1996, the disclosure of which is hereby incorporated by reference, Don Coppersmith has analyzed the security of the Vanstone methods, and found that all but one of Vanstone's methods provide inadequate security. Specifically, for the Vanstone methods having predetermined high order bits, the RSA modulus n is generated in such a way that somewhat more than the high order ((¼)log2 n) bits of p are revealed to the public, which enables discovery of the factorization of the RSA modulus n, thus leaving the scheme vulnerable to attack.